Rule-based languages, used in artificial intelligence applications such as expert systems, are advantageous when there is a large amount of data to be searched and actions are taken based on the results of the search. In order to minimize the searching through this large amount of data, rule-based languages take the information that is available about what is the best approach to a problem and attempt a solution.
A single instruction in a rule-based language takes the form of "when these conditions are met, then do these actions". In other words, the instruction checks to see if certain conditions are met, and if they are, then a number of actions are performed. In a rule-based language, there is no organized flow of control, rather the computer will look for situations and patterns. In other words, a rule-based language is a pattern matching language. For example, one of the instructions may be "when there is object of type A, an object of type B and an object of type C in the data base, then do X, do Y and do Z".
In all rule-based languages, there is a distinction made between the types of data and instances of those types. This distinction is exactly analogous to the distinction made in data bases between a record format and actual records. For example, a particular application could declare a type, BOOK. All instances of the type BOOK contain the same kinds of information: a title, an author, a catalog number, and a page count. This application could then create an instance of type BOOK for each book in the town library. One such instance might contain the following information.
title: "Artificial Intelligence and You"
author: Smith, John
catalog number: 0-670-81442-3
page count: 285
This instance of type BOOK (also referred to as data of type BOOK, an object of type BOOK, or a BOOK object) could potentially satisfy any condition in any rule which is searching for an object of type BOOK.
When the notation of "type inheritance" is introduced, which is a powerful extension to the capabilities of a rule-based language, the situation becomes more complicated. Type inheritance involves the concept of one object type being a subtype of another object type. For example, in a particular application, the type CAT could be declared to be a subtype of the type MAMMAL, and MAMMAL a subtype of VERTEBRATE, and VERTEBRATE a subtype of ANIMAL. The type CAT inherits certain features of the type MAMMAL, since it is a subtype. Examples of features that the subtype CAT inherits from the parent type MAMMAL (i.e. the supertype) could include the characteristics of nursing its young, warm-blooded, etc. The other thing which a type inherits from its parent type is membership. Although any object is an instance of one and only one type, it can usually be used as if it were an instance of any of its supertypes. Thus, a CAT object could satisfy a requirement for an instance of type MAMMAL, or a requirement for an ANIMAL.
Type inheritance is a powerful concept because it maps directly to the way the real world is described by human beings. The English language already has categories like ANIMAL, sub-categories like MAMMAL, and sub-sub-categories like CAT, and instances like John Smith's 3 year old siamese cat. If a school teacher says, "Bring in an animal for show and tell," then every child in the class would know that John Smith's 3 year old siamese cat would satisfy the teacher's request, but so also would a frog or a hamster.
Using a rule-based programming language, a computer will attempt to match every piece of data against every type or subtype that appears as a pattern being matched. For example, if the pattern being matched is MAMMAL, the computer will compare the type of every piece of data in the data base against the type MAMMAL and every subtype of MAMMAL. If a MAMMAL is being searched for among the data to satisfy a rule, then any data of type CAT should satisfy the requirement for a MAMMAL, since CAT is a subtype of MAMMAL. To do this method of searching and matching, however, the type/subtype relationships between the types (a "type hierarchy") must be known.
The determination of the subtype relationship (i.e. whether a specified type is equal to or is a subtype of some other specified type), and more specifically the membership relationship (i.e. whether a specific object can be treated as if it were an instance of a specified type, which is true if and only if the type of the object is equal to or is a subtype of the specified type), is a critical operation in the overall performance of a pattern matching language, such as a rule-based language. Therefore, the determination should be done as quickly as possible, but without greatly increasing the memory space. The term "single inheritance" means that a subtype can have only one immediate parent type in the type hierarchy.
One method of determining membership involves checking the type of the data to see whether that type is the same type as the type that is being matched, and if that fails checking the supertype of the data against the match type. This checking is done against subsequently higher and higher supertypes until either the supertype and the match type are equivalent (i.e. the object is a member of the match type), or there are no more supertypes to compare (i.e. not a member of the match type). With such an approach, a large number of levels may have to be searched before a match or a mismatch is found. For example, it takes two checks to determine that a CAT object can satisfy a match type of MAMMAL; first CAT is compared to MAMMAL, then the supertype of CAT, MAMMAL is compared to MAMMAL and found to be equivalent. However, to determine that the same CAT object will not satisfy a match type of VEGETABLE takes four checks: CAT compared to VEGETABLE, MAMMAL compared to VEGETABLE, VERTEBRATE compared to VEGETABLE, and ANIMAL compared to VEGETABLE. Such an approach, because of these multi-level searches, especially on mismatches (which are almost always far more common than matches), would degrade the performance of a rule-based language to a totally unacceptable level.
Another approach to determining the subtype relationship is to link a set of comparisons together with logical OR's. For example, if a condition in a rule will match if it finds an instance of a MAMMAL, then this is equivalent to matching if it finds a MAMMAL object, or a CAT object, or a DOG, or a HORSE, or a COW, et cetera, for all the subtypes of MAMMAL, and for all sub-subtypes and sub-sub-subtypes, et cetera. This approach becomes very slow and cumbersome whenever the type hierarchy is of any appreciable size.
Another approach for providing knowledge of the subtype relationship would be to provide N.sup.2 space in memory when N is the total number of types. Each axis would list each of the separate types in a grid format. Every point in the grid corresponds to an intersection of one type with another type and will contain a bit. If the bit is a 1, then the type (such as CAT) on one axis is a subtype of the type on the other axis of the grid, for example, MAMMAL. If the bit is a 0, then the type (CAT) on one axis of the grid is not a subtype of the type on the other axis of the grid (for example, AMPHIBIAN). The obvious drawback to this approach is the extremely large amount of memory space that would be needed when the total number of types in an application is large; for example, when N is equal to 10.sup.4, (an entirely reasonable number of types for an application--e.g. the number of parts in a modern aircraft) the amount of memory space needed would be 10.sup.8.
There is therefore a need for a method of quickly determining the subtype relationship in a single inheritance type hierarchy, which finds usefulness in computer programmed with a rule-based language, without increasing greatly the amount of memory space or instructions needed for implementation.